package com.lyj.sc.dynamicProgramming.test20220716;

/**
 * @Author: liyangjing
 * @Date: 2022/07/16/10:02
 * @Description: 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 */
public class canPartition1 {
    public boolean canPartition(int[] nums) {
        //求一半
        int sum = 0;
        for(int n:nums){
            sum+=n;
        }
        if(sum%2!=0){
            return false;
        }
        sum=sum/2;
        //1.把sum看成背包 nums 看成 价值重量 定义dp数组
        int [] dp = new int[sum+1];
        //2.初始化 全部为0
        //3.遍历循环 先遍历物品 在遍历背包
        for(int i=0;i<nums.length;i++){
            for(int j=sum;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        //4.得出结果
        return dp[sum]==sum;
    }
}
